package com.lyj.sc.SecondBruchToReview.hash20220721;

import java.util.*;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-20 17:33
 * @version: 1.0
 * @Modifier By:
 **/
public class Solution {

    // 242.有效的字母异位词
    public boolean isAnagram(String s, String t) {
        //hash
        int [] nums = new int[26];
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        for (char c : s1) {
            nums[c-'a']++;
        }
        for (char c : t1) {
            nums[c-'a']--;
        }
        for (int num : nums) {
            if(num!=0){
                return false;
            }
        }
        return true;
    }

    // 349. 两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        //采用Set 集合
        HashSet<Integer> set = new HashSet();
        HashSet<Integer> set1 = new HashSet();
        for (int i : nums1) {
            set.add(i);
        }
        for (int i : nums2) {
            if(set.contains(i)){
                set1.add(i);
            }
        }
        int[] a = new int[set1.size()];
        int index=0;
        for (Integer integer : set1) {
            a[index++]=integer;
        }
        return a;
    }

    // 202. 快乐数
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while (n!=1){
            if(set.contains(n)){
                return false;
            }
            set.add(n);
            n=happy(n);
        }
        return true;
    }
    // 202函数
    public int happy(int n){
        int sum = 0;
        while (n!=0){
            int temp = n % 10;
            sum+=temp*temp;
            n=n/10;
        }
        return sum;
    }

    // 1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] n = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target-nums[i])){
                n[0]=i;
                n[1]=map.get(target-nums[i]);
                return n;
            }
            map.put(nums[i],i);
        }
        return n;
    }

    // 383. 赎金信
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        char[] r = ransomNote.toCharArray();
        for (int i = 0; i < r.length; i++) {
            if(map.containsKey(r[i])){
                map.put(r[i],map.getOrDefault(r[i],0)+1);
                continue;
            }
            map.put(r[i],1);
        }
        char[] t = magazine.toCharArray();
        for (int i = 0; i < t.length; i++) {
            if(map.containsKey(t[i])){
                Integer temp = map.get(t[i]);
                map.put(t[i],temp-1);
            }
        }
        for (int i = 0; i < r.length; i++) {
            if(map.get(r[i])>0){
                return false;
            }
        }
        return true;
    }

    // 第15题. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                return list;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }

            int sum = -nums[i]; //1
            int left = i+1;
            int right = nums.length-1;
            while (left<right){
                //区分sum
                if(sum<(nums[left]+nums[right])){
                    right--;
                }else if(sum>(nums[left]+nums[right])){
                    left++;
                }else if(sum==(nums[left]+nums[right])) {
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    // not if while
                    while (left<right && nums[right] == nums[right-1]){
                        right--;
                    }
                    while (left<right && nums[left] == nums[left+1]){
                        left++;
                    }
                    left++;
                    right--;
                }
            }
        }
        return list;
    }

    // 第18题. 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //双指针 nums
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        //i
        for (int i = 0; i < nums.length; i++) {
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for (int j = i+1; j < nums.length; j++) {
                /// FIXME: 2022/7/21
                if(nums[i] > target && nums[i]>0){
                    break;
                }
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while (left<right){
                    //区分sum
                    int sum =nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum<target){
                        left++;
                    }else if(sum>target){
                        right--;
                    }else{
                        list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        // not if while
                        while (left<right && nums[right] == nums[right-1]){
                            right--;
                        }
                        while (left<right && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return list;
    }

    // 454. 四数相加 II
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int num = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                int temp = i+j;
                if(map.containsKey(temp)){
                    map.put(temp,map.get(temp)+1);
                }
                else {
                    map.put(temp,1);
                }
            }
        }

        for (int i : nums3) {
            for (int j : nums4) {
                int temp = 0-(i+j);
                if(map.containsKey(temp)){
                    num+=map.get(temp);
                }
            }
        }
        return num;
    }
}
